public class mysingleList {


    static class Node{
        public int val;
        public Node next;
        public Node(int val){
            this.val=val;
        }
    }
    public Node head;//代表头节点

    public void createLink(){
        Node node=new Node(12);
        Node node1=new Node(45);
        Node node2=new Node(23);
        Node node3=new Node(90);
        Node node4=new Node(100);
        node.next=node1;//node代表一种引用，是地址类型
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        head=node;
    }
    //遍历链表
    public void display(){
        Node cur=head;
        while(cur!=null){
            System.out.println("cur.val="+cur.val);
            cur=cur.next;
        }
    }
    //从指定位置开始展示
    public void display(Node Head){
        Node cur=head;
        while(cur!=null){
            System.out.println("cur.val="+cur.val);
            cur=cur.next;
        }
    }
    public boolean contains(int key){
        Node cur=head;
        while(cur!=null){
            if (cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //计算单链表长度
    public int size(){
        int count=0;
        Node cur=head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //头插法
    public void addFirst(int data){
        Node node =new Node(data);
        node.next=head;
        head=node ;
    }
    //尾插法
    public void addLast(int data){
        Node node=new Node(data);
        if (head==null){
            head=node;
            return;
        }
        Node cur=head;
        while(cur.next!=null){//找到尾巴
            cur=cur.next;
        }
        cur.next=node;
    }
    //指定位置插入
    public void addIndex(int index,int data) {
        checkIndex(index);
        if (index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
        }
        Node cur=findIndexSubOne(index);
        Node node =new Node(data);
        node.next=cur.next;
        cur.next=node;
    }
    private Node findIndexSubOne(int index){
        Node cur=head;
        int count=0;
        while(count!=index-1){
            cur=cur.next;
            count++;
        }
        return cur;
    }
    //检查下标合法
    private void checkIndex(int index){
        if (index<0||index>size()){
            System.out.println("index位置不合法");
            return;
        }
    }
    //删除第一出线的Key关键字
    public void remove(int key){
        if(head.val==key){//如果头节点为key
            head=head.next;
            return;
        }
        Node cur=searchPrev(key);//要删除节点的前一个节点
        if (cur==null){
            return;
        }
        Node del=cur.next;//要删除的节点
        cur.next=del.next;//要删除节点的下一个节点赋值给cur的next位置
    }
    //找key的前一个节点
    private Node searchPrev(int key){
        if (head==null){
            return null;
        }
        Node cur=head;
        while (cur!=null){
            if (cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
    //删除所以key节点
    //移动，未找到分支cur=cur.next，找到key分支,删除,cur.next=cur.next.next
    //选择分支里判断链接的下一个节点是否key,cur.next.val==key
    public void removeAllkey(int key){
        if (head==null){
            return ;
        }
        /*while (head.val==key){//处理头节点为key方法一
            head=head.next;
        }*/
        Node prev=head;
        Node cur=head.next;

        while(cur!=null){
            if (cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else {
                prev=cur;
                cur=cur.next;
            }
        }
        //处理头节点方法二
        if (head.val==key){//由于此时是走完while循环的，后面的元素一定没有key元素，开始处理头节点有key的情况
            head=head.next;
        }
    }
    //回收
    public void clear(){
        head=null;
    }
    //链表反转
    public Node reverseList(){//返回新的头节点
        if (head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        Node cur=head.next;
        head.next=null;
        while(cur!=null){
            Node curNext=cur.next;
            cur.next=head;
            head=cur;//把cur当成新的头节点
            cur=curNext;
        }
        return head;
    }
    public Node middleNode(){
        Node fast=head;
        Node slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //返回倒数第k个节点
    public Node findKthTotail(int k){//k是倒数第k个
        if (k<0||k>size()||head==null){
            return null;
        }
        /*思路
         * 先让fast走k-1步，然后fast和slow一起走1步
         * fast.next==null时循环结束，返回slow，slow既是倒数第k个节点*/

        /*例如求倒数第4个节点，fast先走4-1=3步，然后当slow走到倒数第四个时，fast一定走到最后一个节点*/
        Node fast=head;
        Node slow=head;
        while(k-1!=0){//fast和slow相差k-1步
            //例如倒数第1个，
            fast=fast.next;
            k--;
        }
        while(fast!=null&&fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    //判断链表是否回文
    /*1.奇数找到中间节点
     * 2.后（n-1）/2个链表反转
     * h1.val==h2.val,移动*/
    public boolean chkPalindrome(){
        if(head==null){
            return false;
        }
        if (head.next==null){
            return true;
        }
        Node fast=head;
        Node slow=head;
        //找到中间节点
        while(fast!=null&& fast.next!=null ){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转
        Node cur=slow.next;//cur代表当前需要反转的节点
        while(cur!=null){
            Node curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //3.前后对比判断相等
        while(slow!=head){
            //值不相等的情况进入改分支
            if(slow.val!=head.val){
                return false;
            }
            //以下为值相等的情况
            if (head.next==slow){//偶数的情况判断
                return true;
            }
            slow=slow.next;
            head=head.next;
        }
        return true;
    }
    public Node partition( int x) {
        // write code here
        Node be=null;
        Node bs=null;
        Node ae=null;
        Node as=null;
        Node cur=head;
        while(cur!=null){
            if (cur.val<x){
                if (bs==null){//第一次插入
                    be=cur;
                    bs=cur;

                }else{
                    be.next=cur;//建立链接,bs不动
                    be=be.next;//be也要动
                }
            }else{
                if (as==null){
                    ae=cur;
                    as=cur;

                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        //处理都大于或者都小于的情况，此时bs或as有一边为空
        if (be==null){//如果第一段为空
            return as;//返回第二段的头节点
        }
        //第一段不为空的情况，循环走完后,两分割链表链接
        be.next=as;
        //如果第二段不为空
        //最后一个节点置null
        if (ae!=null){
            ae.next=null;
        }
        return bs;
    }
    //判断是否有环,快慢指针
    public boolean hasCycle(Node head) {
        Node fast=head;
        Node slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                return true;//找到返回true
            }
        }
        return false;//循环走完没进入到if语句，证明没有环，是单向链表
    }
    //找出相遇的点
    public Node detectCycle() {
        //先判断有无环
        Node fast=head;
        Node slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                break;//相遇，证明找到相遇点，跳出循环
            }
        }
        if (fast==null||fast.next==null){
            return null;
        }
        //fast不为null的情况，slow回归头节点
        slow=head;
        //公式X=（N-1）R+Y，fast和slow同时走，fast走完N圈+Y的路程后，slow走完X的路程，slow刚好到环的入口
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;//返回环的入口

    }
}

